//
//  CCSortedAndSearch.hpp
//  leetcode
//
//  Created by hellobike07499 on 2019/8/14.
//  Copyright © 2019 hellobike07499. All rights reserved.
//

#ifndef CCSortedAndSearch_hpp
#define CCSortedAndSearch_hpp

#include <stdio.h>
#include <vector>
#include <iostream>
using namespace std;

class CCSortedAndSearch{
public:
    void  test(){
        test2();
    }
    void test1(){
        vector<int> num1 = {1,2,3, 0, 0, 0};
        vector<int> num2 = {2,5,6};
        
        merge(num1, 3, num2, 3);
        cout << "abc" << endl;
    }
    
    void test2(){
        cout << firstBadVersion(100) << endl;
    }
private:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> sub(nums1.begin(), nums1.begin() + m);
        
        int i = 0;
        while (!nums2.empty() && !sub.empty()) {
            if(nums2[0] < sub[0]){
                nums1[i] = nums2[0];
                nums2.erase(nums2.begin());
            }else{
                nums1[i] = sub[0];
                sub.erase(sub.begin());
            }
            i++;
        }
        
        while(i < nums1.size()){
            if(nums2.size() > 0){
                nums1[i] = nums2[0];
                nums2.erase(nums2.begin());
            }else if(sub.size() > 0){
                nums1[i] = sub[0];
                sub.erase(sub.begin());
            }
            i++;
        }
    }
    
    bool isBadVersion(int version){
        return version >= 5;
    }
    int firstBadVersion(int n) {
        if(isBadVersion(0)) return 0;
        
        int first = 0;
        int end = n;
        while(first != end){
            if(first == (end - 1)){
                first = end;
            }
            int c = first + (end - first) / 2;
            
            if(isBadVersion(c)){
                end = c;
            }else{
                first = c;
            }
        }
        return first;
    }
    
};


#endif /* CCSortedAndSearch_hpp */
